package it.unisa.ingegneria.tdp.esercitazione5;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * Classe che implementa la visita in ampiezza(BFT)
 * 
 */
public class BFS<T> {
	private Graph<T> graph;
	private MyVertex<T> source;

	public BFS(Graph<T> g)
	{
		this.graph=g;
	}

	public String breadthFirstSearch(MyVertex<T> s)
	{
		String stampaTest = "";
		this.source=s;
		int index=0;
		Iterator<MyVertex<T>> i =  graph.vertices().iterator();
		ArrayList<MyVertex<T>> Q= new  ArrayList<MyVertex<T>> (); 
		Iterator<MyVertex<T>> adj;
		MyVertex<T> temp;
		MyVertex<T> u;
		MyVertex<T> v;
		System.out.println("Vertice di partenza " + s.toString());
		stampaTest += s.toString();
		
		while(i.hasNext())
		{
			temp=i.next();
			temp.setParent(null);
			temp.setDecorator("color", 0);
		}

		source.setParent(null);
		source.setDecorator("color",1); 
		Q.add(index, source);
		while(!Q.isEmpty())
		{
			u=Q.remove(index);
			index=index-1;
			adj= u.outgoingVertexes().iterator(); 
			while(adj.hasNext())
			{
				v=adj.next();
				if(v.getDecorator("color").equals(0))
				{
					v.setDecorator("color",1);
					v.setParent(u);
					index=index+1;
					Q.add(index, v);
					System.out.println("Vertice " + v.toString());
					stampaTest += v.toString();
				}
			}
			u.setDecorator("color",2);
		}
		return stampaTest;
	}

}
